/*
 * Types.h
 *
 *  Created on: 24/apr/2013
 *      Authors: Ialenti Andrea, Marangon Fabio
 */

#ifndef TYPES_H_
#define TYPES_H_

#include "StatusCodes.h"

#include "../lib/plot/gnuplot_i.h"

#include <ilcplex/cplex.h>

typedef gnuplot_ctrl	plotter;

//	Data type used to represent a node by its (x, y) coordinates and ID.
struct _Node {
	int id;					//	Node ID.
	double x;				//	Node 'x' coordinate.
	double y;				//	Node 'y' coordinate.
	int degree;				//	Number of edges connected to the node.
	int forced;				//	Number of edges connected to the node that are forced in the branch and bound.
};
typedef struct _Node 	Node;

struct _Edge {
	Node *start;			//	One of the two nodes connected to the edge.
	Node *end;				//	One of the two nodes connected to the edge.
	double cost;			//	Edge cost.
	struct _Edge *prev;		//	Link to the next edge in a path.
	struct _Edge *next;		//	Link to the previous edge in a path.
};
typedef struct _Edge	Edge;

//	Data type used to represent a random graph.
struct _Graph {
	int size;				//	Graph size (number of nodes).
	int edgeCnt;			//	Total number of edges in the graph.
	int seed;				//	Pseudo random number generator seed.
	double min;				//	The minimum coordinate value.
	double max;				//	The maximum coordinate value.
	Node *nodes;			//	Graph nodes array.
	Edge **edges;			//	Graph edges matrix (storing (i, j) pairs with costs).
	double **costs_origin;	//	Graph edges original costs matrix.
	double *u;				//	Graph lagrangian coefficients.
	char *name;				//	Graph name.
};
typedef struct _Graph	Graph;

//	Data type used to represent the 1-tree.
struct _OneTree {
	int size;				//	Number of nodes in the tree.
	int v0;					//	The node to be considered as v0.
	int i1, i2;				//	Indices for the 2 min-cost edges starting in node v0.
	Node *nodes;			//	Tree nodes array.
	Edge *edges;			//	Tree edges array (storing (i, j) pairs with costs).
	double **costs;			//	Tree cost matrix.
	double totalCost;		//	Total cost of the tree (original graph costs).
	double tc;				//	Total cost of the tree (lagrangian-modified costs).
	char *name;				//	1-tree name.
};
typedef struct _OneTree	OneTree;

//	Data type used to represent the function L(uk).
struct _funcLu {
	int size;				//	Number of values in the function (or maximum number of iterations).
	int step;				//	Iterations without improvements before updating the alpha.
	double *L;				//	Array for the ordinate.
	double best;			//	The best lower bound found.
	int kBest;				//	The k value corresponding to the best lower bound found.
	double upperBound;		//	Function upper bound.
	char *name;				//	Function name.
};
typedef struct _funcLu	funcLu;

//	Data type used to create the CPLEX problem.
struct _Problem {
	int nodes;				//	Number of nodes in the graph.
	int edges;				//	Number of edges in the graph.
	int *Xe;				//	Array containing the (up to) n² variables Xe.
	double *XeCost;			//	Array containing the cost 'Ce' associated to edge 'Xe'.
	int **pos;				//	Matrix containing the position the edges (i,j) given the Xe.
	int **posReverse;		//	Matrix containing the two Xe of a node i
	double probLB;			//	Problem lower bound (found using the lagrangian relaxation).
	double probUB;			//	Problem upper bound (found using the heuristic algorithm).
	char *name;				//	Problem name.
	char **varNames;		//	Problem variables names.
	char **constrNames;		//	Problem constraint names.
	int *constrIdx;			//	Problem constraint indices.

	//	CPLEX-related variables.
	char *probname;			//	Problem name.
	int numcols;			//	Number of columns in the constraint matrix.
	int numrows;			//	Number of rows in the constraint matrix.
	int nonZero;			//	Number of non-zero coefficients in the constraint matrix.
	int objsen;				//	Type of problem (min or max).
	double *objCoeff;		//	Coefficients for the object function.
	double *rhs;			//	Right hand side values for the constraint.
	char *sense;			//	Constraint type.
	int *matbeg;			//	Constraint column index.
	int *matcnt;			//	Number of variables per column in the constraint matrix.
	int *matind;			//	Constraints row index.
	double *matval;			//	Variables coefficients in the constraints.
	double *lb;				//	Lower bound on variables.
	double *ub;				//	Upper bound on variables.
	char *ctype;			//	Variables type.

	//	CPLEX-related variables used for the proximity search method.
	double heuSol;			//	Heuristic solution.
	double *vals;			//	Graph edges costs.
	int beg[1];				//	Index for the 'matbeg' in the 'CPXaddrows'.
	int *idx;				//	'matind' for the 'CPXaddrows'.
	char **psName;			//	Proximity search constraint name.
};
typedef struct _Problem	Problem;

//	Data type used to memorize a Sub-tour Elimination Constraint (SEC).
struct _SEC {
	int size;				//	Maximum number of variables in the SEC.
	int nonZero;			//	Actual number of variables.
	char *constrName[1];	//	Constraint name.
	double rhs[1];			//	Right hand side value for the constraint.
	char sense[1];			//	Constraint type, this should always be 'L'.
	int *matbeg;			//	Constraint column index.
	int *matind;			//	Constraints row index.
	double *matval;			//	Variables coefficients in the constraints.
};
typedef struct _SEC		SEC;

//	Boolean data type
enum _bool {
	false,
	true
};
typedef enum _bool		bool;


//	Data type used to store all the program configuration parameters.
struct _cfg {
	//	Constants useful in reading TSP lib graphs.
	int MAX_LINE_LEN;
	double PI;
	double RADIUS;

	//	Default parameters.
	bool DFLT_VERBOSITY;	//	Program verbosity.
	char *DFLT_PROB;		//	Default TSP-lib instance.
	bool DFLT_USE_PS;		//	Flag to activate the proximity search method.
	bool DFLT_USE_CPLEX;	//	Flag to activate the CPLEX.
	bool DFLT_USE_CB;		//	Flag to activate the CPLEX callbacks.
	bool DFLT_NODE_PERM;	//	Flag to activate graph nodes permutation.
	bool DFLT_USE_3OPT;		//	Flag to activate 3-opt algorithm.

	//	Constants used in the Lagrangian relaxation and in the heuristics.
	double UB_INC;			//	Upper bound increase step.
	int RAND_STEP;			//	Steps before randomizing the u's.
	int MAX_IT;				//	Maximum number of iterations.
	int STEP;				//	Iterations without improvements before updating the alpha.
	int IT_3OPT;			//	Number of iterations of 3-Opt moves for every 2-Opt solution.

	//	Constants useful when plotting graphs, 1-trees, and TSP solutions.
	int SIZE_H;				//	Windows vertical size.
	int SIZE_W;				//	Windows horizontal size.
	char *TERM_X;			//	Terminal type.
	char *COLOR_BLUE;
	char *COLOR_BLACK;
	char *COLOR_RED;
	char *COLOR_GREEN;
	char *PLT_PATH;			//	Path for the plot files.

	//	Constant used to define the ∞ cost, used to force or deny a graph edge..
	long INF;

	//	Constant used to avoid numeric errors.
	double EPS;

	//	Maximum length for names in the program.
	int NAME_LEN;
	int CSTR_NAME_LEN;

	//	CPLEX-related constants.
	int CPX_TH_CNT;			//	Number of threads to be used.
	int CPX_CB_PLT;			//	How many solution should the callback plot (the bigger this number, the less the plots).
	char *CPX_PS_C_NAME;	//	Proximity search constraint name.
	char *CPX_FILE_PATH;	//	Path where to store CPLEX problem files.
	double CPX_PS_TL;		//	CPLEX time limit (seconds) for MIP opt runs during the proximity search algorithm.
	double CPX_PS_ML;		//	CPLEX memory limit (MB) for proximity search.
	int CPX_PS_GTL;			//	Global time limit (seconds) for the proximity search algorithm (this limit will scale with problem size).
	double CPX_TIME_LIM;	//	CPLEX time limit (seconds), 12 hours.
	double CPX_MEM_LIM;		//	CPLEX memory limit (megabytes), 120GB.

	//	Normalization time coefficient.
	double NORM_TIME;

	//	Branch and bound parameters.
	int B_B_OUTPUT;			//	Output frequency parameter.
	int B_B_TIME_LIMT;		//	Time limit for the branch and bound method.

	plotter *plt;			//	Reference to the GNU plot handler.
};
typedef struct _cfg		Config;

//	Data type used to store the information to be passed to the callback.
struct _cbData {
	CPXLPptr lp;			//	CPLEX problem.
	Problem *p;				//	Reference to the problem we created.
	Graph *g;				//	Reference to the graph.
	int numcols;			//	Number of columns in the current CPLEX solution.
	int totSECs;			//	Counter for the total number of SECs added by all the callbacks.
	int solCnt;				//	Counter for the total number of solutions calculated.
	double *x;				//	Array used to store the CPLEX solution.
	double totalCost;		//	Solution cost.
	int cntLSSol;			//	Lazy SEC callback solution counter.
	double bestLSSol;		//	Best integer solution found using lazy SEC callback.
	int cntLS;				//	Lazy SEC callback counter.
	int cntMC;				//	Min cut callback actual counter.
	int cntMCTot;			//	Min cut callback total counter.
	bool verbose;			//	Callbacks verbosity.
	const Config *cfg;			//	Program configuration data.
};
typedef struct _cbData	cbData;

//	Data type used to represent a line segment.
struct _Line {
	double sX, sY;			//	Starting coordinates (x, y).
	double eX, eY;			//	Ending coordinates (x, y).
};
typedef struct _Line	Line;

//	Data type to enumerate the supported TSP-lib data format.
enum _TSPLib {
	EUC_2D,
	GEO,
	CEIL_2D,
	EXPLICIT
};
typedef enum _TSPLib	TSPLib;

//	Function used to allocate the memory used by the graph data structure.
bool initGraph(const Config *cfg, Graph *g, int nodes, int seed);

//	Function used to allocate the memory used by the 1-tree data structure.
bool initOneTree(const Config *cfg, OneTree *t, int nodes);

//	Function used to allocate the memory for the function L(u(k)).
bool initFuncLu(const Config *cfg, funcLu *f, int size, int step);

//	Function used to allocate the memory for the problem data structure.
bool initProblem(const Config *cfg, Problem *p, int nodes, int actualEdges);

//	Function used to allocate the memory for the SEC data structure.
bool initSEC(const Config *cfg, SEC *s, int nodes);

//	Function used to allocate memory for an array of SECs.
bool initSECsArray(const Config *cfg, SEC **s, int size, int nodes);

//	Function used to initialize the 'cdData' data structure.
bool initCBData(const Config *cfg, cbData *data, Graph *g, Problem *p, CPXLPptr *lp, bool verbose);

//	Function used to initialize the configuration data.
Status initCfgData(Config *cfg, const char *fileName);

//	Function used to free the memory used by the graph data structure.
void disposeGraph(Graph *g);

//	Function used to free the memory used by the 1-tree data structure.
void disposeOneTree(OneTree *t);

//	Function used to free the memory used by the function L(u(k)).
void disposeFuncLu(funcLu *f);

//	Function used to free the memory used by the problem data structure.
void disposeProblem(Problem *p);

//	Function used to free the memory used by the SEC data structure.
void disposeSEC(SEC *s);

//	Function used to free the memory used by the array of SECs.
void disposeSECsArray(SEC *s, int size);

//	Function used to implement nodes deep copy.
void cpNode(const Node *src, Node *dest);

#endif /* TYPES_H_ */
